#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<mpi.h>
#include<time.h>
#include<iostream>
#include<list>

using namespace std;

#define TAM_MAX_PALAVRA 100
#define TAM_MAX_FRASE 200
#define BILLION 1E9

/* Retorna 1 se a string é um palindromo, se não retorna 0 */
int palindromo(char string[]){
	int i, tam, tam_aux, flag = 1;
	char string_aux[TAM_MAX_PALAVRA];

	strcpy(string_aux, string);

	tam = strlen(string_aux);
	tam_aux = tam/2;

	for(i = 0; i < tam; i++)
		if(isupper(string_aux[i]))
			string_aux[i] = tolower(string_aux[i]);

	for(i = 0; i < tam_aux; i++){
		if(string_aux[i] != string_aux[tam-i-1])
			flag = 0;
	}

	return flag;
}

/* Faz o pre-processamento do arquivo shakespe.txt e separa ele em (noProcesses-1) arquivos */
void separaArquivo(int noProcesses){
	int num_frases = 0, i;
	char aux_arq[5], c, c_ant;
	FILE *fp, *fp_out[noProcesses-1];

	strcpy(aux_arq, "k.txt");

	/* Abrimosos arquivos 0.txt, 1.txt, ..., (noProcesses-2).txt */
	for(i = 0; i < noProcesses-1; i++){
	        aux_arq[0] = (char)(((int)'0')+i);
	        fp_out[i] = fopen(aux_arq, "w+");
	}

	/* Vamos realizar o pré-processamento do texto e separa-lo */
	fp = fopen("shakespe.txt", "r+");
	i = 0;
	c = fgetc(fp);
	c_ant = 'a';
	while(c != EOF){
	        /* Se for diferente de numeros ou letras, colocamos _, se for fim de linha colocamos * */
		if (c == '\n')
			fputc('*', fp_out[i]);
		else if(!(c >= '0' && c <= '9') && !(c >= 'a' && c <= 'z') && !(c >= 'A' && c <= 'Z'))
			fputc('_', fp_out[i]);
		else
			fputc(c, fp_out[i]);

	        /* Se é fim de linha, e o caracter anterior não é, quer dizer que chegamos no final de uma frase */
	        if(c == '\n' && c_ant != '\n')
	                num_frases++;

	        /* Se o número de frases for igual ao 127568/noProcesses-1, mudamos o arquivo */
	        if(num_frases == (127568/(noProcesses-1)) && i != (noProcesses-2)){
	                i++;
	                num_frases = 0;
	        }
		c_ant = c;
        	c = fgetc(fp);
	}

	/* Fecha os ponteiros de arquivo abertos */
	fclose(fp);
	for(i = 0; i < noProcesses-1; i++)
		fclose(fp_out[i]);
}

/* Esta função recebe um array de listas e um rank, para o rank 1 a função pega o arquivo 0.txt 
 * e coloca as palavras dele na lista palavras[0] */
void separaListasPalavras(list<string> *palavras, int rank){
	char c, aux_arq[5], palavra[TAM_MAX_PALAVRA];
	int flag, i;
	FILE *fp_final;

	list<string>::iterator it = palavras[rank-1].begin();

	strcpy(aux_arq, "k.txt");

	/* Abrimos o arquivo, se estamos no rank 1, abrimos o arquivo 0.txt */
	aux_arq[0] = (char)(((int)'0')+(rank-1));
	fp_final = fopen(aux_arq, "r+");

	/* Agora voltamos para o inicio do arquivo e separamos as palavras */
	c = fgetc(fp_final);
	i = 0;
	while(c != EOF){
		if(c != '_' && c != '*') /* nosso delimitador é _ */
			palavra[i++] = c;
		else if (i != 0)
			flag = 1;

		if(flag == 1){
			palavra[i] = '\0';
			if(i > 1)
				palavras[rank-1].insert(it, palavra);
			i = 0;
			flag = 0;
		}
		c = fgetc(fp_final);
	}

	fclose(fp_final);
}

/* Esta função recebe um array de listas e um rank, para o rank 1 a função pega o arquivo 0.txt 
 * e coloca as frases dele na lista frases[0] */
void separaListasFrases(list<string> *frases, int rank){
	char c, aux_arq[5], frase[TAM_MAX_FRASE];
	int flag, i;
	FILE *fp_final;

	list<string>::iterator it = frases[rank-1].begin();

	strcpy(aux_arq, "k.txt");

	/* Abrimos o arquivo, se estamos no rank 1, abrimos o arquivo 0.txt */
	aux_arq[0] = (char)(((int)'0')+(rank-1));
	fp_final = fopen(aux_arq, "r+");

	/* Agora voltamos para o inicio do arquivo e separamos as palavras */
	c = fgetc(fp_final);
	i = 0;
	while(c != EOF){
		if(c != '_' && c != '*') /* nosso delimitador é *, _ é ignorado */
			frase[i++] = c;
		else if (c == '*' && i != 0)
			flag = 1;

		if(flag == 1){
			frase[i] = '\0';
			if(i > 1)
				frases[rank-1].insert(it, frase);
			i = 0;
			flag = 0;
		}
		c = fgetc(fp_final);
	}

	fclose(fp_final);
}

/* Retorna o numero de palindromos que foram encontrados na lista passada como argumento */
int numeroPalindromos(list<string> *lista, int rank){
	int i, num_palindromos = 0;
	char aux_string[200];
	list<string>::iterator it;
	string aux;

	/* Percorre a lista procurando palindromos, excluimos as palavras que não são aplindromos da lista */
	for(it=lista[rank-1].begin(); it != lista[rank-1].end(); it++){
		aux = *it;

		/* Passamos a palavra de string (c++) para um array de chars (c) */
		for(i = 0; i < aux.size(); i++)
			aux_string[i] = aux[i];
		aux_string[i] = '\0';

		if(palindromo(aux_string))
			num_palindromos++;
	}

	return num_palindromos;
}

int main(int argc, char **argv){
	int k, num_palindromos = 0, num_palindromos_frase = 0;
	int a, b, c, sinal;
	int rank, noProcesses;
	struct timespec time1, time2, time3, time4;
	double diff;

	/* Inicializamos MPI */
	MPI_Init(&argc, &argv);
	MPI_Comm_size(MPI_COMM_WORLD, &noProcesses);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	MPI_Status Stat;

	list<string> palavras[noProcesses-1];
	list<string> frases[noProcesses-1];
	list<string>::iterator it;
	string aux;

	/* Se estamos no processo 0, o "mestre", vamos separar o arquivo shakespe em vários outros arquivos 
	 * Nos outros processos vamos colocar as palavras e as frases em listas diferentes */
	if(rank == 0){
		separaArquivo(noProcesses);

		/* Da um boradcast para que os outros processos possam continuar */
		MPI_Bcast(&a, 1, MPI_INT, 0, MPI_COMM_WORLD);
	} else {
		/* Esperam o processo mestre */
		MPI_Bcast(&a, 1, MPI_INT, 0, MPI_COMM_WORLD);

		separaListasPalavras(palavras, rank);
		separaListasFrases(frases, rank);

		/* Envia sinal para o mestre que está esperando a separação das listas */
		MPI_Send(&sinal, 1, MPI_INT, 0, rank, MPI_COMM_WORLD);
	}


	/************************ Procura os Palindromos (palavras) ************************/


	/* O processo 0 espera todos estarem prontos para começar a contar o tempo */
	if(rank == 0){
		/* O mestre espera a separação de todas as listas */
		for(k = 1; k < noProcesses; k++)
			MPI_Recv(&sinal, 1, MPI_INT, k, k, MPI_COMM_WORLD, &Stat);

		clock_gettime(CLOCK_REALTIME, &time1);

		/* Da um boradcast para que os outros processos possam continuar */
		MPI_Bcast(&b, 1, MPI_INT, 0, MPI_COMM_WORLD);
	} else {
		/* Esperam o processo mestre */
		MPI_Bcast(&b, 1, MPI_INT, 0, MPI_COMM_WORLD);

		for(k = 1; k < noProcesses; k++)
			if(k == rank){
				num_palindromos = numeroPalindromos(palavras, rank);

				/* Envia sinal para o mestre que está esperando o termino da verificação de palindromos */
				MPI_Send(&num_palindromos, 1, MPI_INT, 0, rank, MPI_COMM_WORLD);
			}
	}

	/* O processo 0 espera todos terminarem para terminar de contar o tempo */
	if(rank == 0){
		/* O mestre espera a verificação de palindromos */
		for(k = 1; k < noProcesses; k++){
			MPI_Recv(&sinal, 1, MPI_INT, k, k, MPI_COMM_WORLD, &Stat);
			num_palindromos += sinal;
		}

		clock_gettime(CLOCK_REALTIME, &time2);

		diff = (time2.tv_sec-time1.tv_sec)+(time2.tv_nsec-time1.tv_nsec)/BILLION;

		printf("Numero de palindromos no texto (palavras) : %d\n", num_palindromos);
		printf("Tempo para verificação de palindromos (palavras): %lf segundos\n",diff);

		clock_gettime(CLOCK_REALTIME, &time3);

		/* Da um boradcast para que os outros processos possam continuar e verificarem os primos */
		MPI_Bcast(&c, 1, MPI_INT, 0, MPI_COMM_WORLD);

	/************************ Procura os Palindromos (frases) ************************/
	} else {
		/* Esperam o processo mestre */
		MPI_Bcast(&c, 1, MPI_INT, 0, MPI_COMM_WORLD);

		for(k = 1; k < noProcesses; k++)
			if(k == rank){
				num_palindromos_frase = numeroPalindromos(frases, rank);

				/* Envia sinal para o mestre que está esperando o termino da verificação de palindromos */
				MPI_Send(&num_palindromos_frase, 1, MPI_INT, 0, rank, MPI_COMM_WORLD);
			}
	}

	if(rank == 0){
		/* O mestre espera a verificação de palindromos */
		for(k = 1; k < noProcesses; k++){
			MPI_Recv(&sinal, 1, MPI_INT, k, k, MPI_COMM_WORLD, &Stat);
			num_palindromos_frase += sinal;
		}

		clock_gettime(CLOCK_REALTIME, &time4);

		diff = (time4.tv_sec-time3.tv_sec)+(time4.tv_nsec-time3.tv_nsec)/BILLION;
		printf("Numero de palindromos no texto (frases) : %d\n", num_palindromos_frase);
		printf("Tempo para verificação de palindromos (frases): %lf segundos\n",diff);
	}

	MPI_Finalize();

	return 0;
}
